package Algorithm.StackAndQueue;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author cj
 * @Date 2021/11/9 20:22
 */
public class getNearLessNoRepeat {

    public static int[][] getNearLessNoRepeat1(int[] arr) {
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                int tmp = stack.peek();
                res[tmp][1] = i;
                stack.pop();
                res[tmp][0] = !stack.isEmpty() ? stack.peek() : -1;
            }
            res[i][0] = !stack.isEmpty() ? stack.peek() : -1;
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int tmp = stack.peek();
            res[tmp][1] = -1;
            stack.pop();
            res[tmp][0] = !stack.isEmpty() ? stack.peek() : -1;
        }
        return res;
    }

    // 进阶：arr可能有重复值
    public static int[][] getNearLessNoRepeat2(int[] arr) {
        int[][] res = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]) {
                List<Integer> popList = stack.pop();
                for (Integer index : popList) {
                    res[index][1] = i;
                    res[index][0] = stack.isEmpty() ?
                            -1 : stack.peek().get(stack.peek().size() - 1);
                }
            }
            if (!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]) {
                stack.peek().add(i);
            } else {
                res[i][0] = !stack.isEmpty() ?
                        stack.peek().get(stack.peek().size() - 1) : -1;
                List<Integer> nowLs = new ArrayList<>();
                nowLs.add(i);
                stack.push(nowLs);
            }
        }
        while (!stack.isEmpty()) {
            List<Integer> popList = stack.pop();
            for (Integer index : popList) {
                res[index][1] = -1;
                res[index][0] = stack.isEmpty() ? -1 : stack.peek().get(0);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {3,4,1,5,6,2,7};
        int[][] res = getNearLessNoRepeat1(arr);
        int[] arr2 = {3,1,3,4,3,5,3,2,2};
        int[][] res2 = getNearLessNoRepeat2(arr2);
    }
}
